package FourthWeek;


import java.util.Arrays;
import java.util.HashSet;

public class Firday {
    //275、H指数 II
    public int hIndex(int[] citations) {
        //例如例子1：[0,1,3,5,6]
        //h等于0，就是至少发0篇，并且至少被引用了0次，null满足，恒成立
        //h等于1，就是至少发1篇，并且至少被引用了1次，[1]满足
        //h等于2，就是至少发2篇，并且至少被引用了2次，[3,5]满足
        //h等于3，就是至少发3篇，并且至少被引用了3次，[3,5,6]满足
        //h等于4，就是至少发4篇，并且至少被引用了4次，不满足
        //第一次不满足后，之后都不会被满足条件，因为是递增的数组
        //我们找的是满足条件的最大值，这里是3
        //我们任意选择一个分割数组的点，如果这个是最大的h，那么，小于h的都是恒成立的，大于h的就是不满足条件的值
        //这样就可以分成二段性, n 为数组的长度
        //citations[mid] < n - mid ,left = mid + 1
        //citations[mid] >= n - mid ,right = mid
        int n = citations.length;
        int left = 0,right = n - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] < n - mid) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return citations[left] >= n - left ? n - left : 0;
    }


    //268、丢失的数字
    public int missingNumber(int[] nums) {
        //位运算
        int ret = 0;
        for (int x : nums) {
            ret ^= x;
        }
        for (int i = 0; i <= nums.length; i++) {
            ret ^= i;
        }
        return ret;
    }
    public int missingNumber2(int[] nums) {
        //先排序在进行和下标进行对比
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0;i < n;i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n;
    }
    public int missingNumber1(int[] nums) {
        //使用哈希表
        HashSet<Integer> set = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n;i++) {
            set.add(nums[i]);
        }
        int ret = -1;
        for (int i = 0; i <= n; i++) {
            if (!set.contains(i)) {
                ret = i;
                break;
            }
        }
        return ret;
    }
}
